package exams.list;

public class ReverseListSolution {

    public static void main(String[] args) {
        int i = 1;
        ListNode currentNode = new ListNode(i);
        ListNode head = currentNode;
        while(i < 10) {
            currentNode.next = new ListNode(++i);;
            currentNode = currentNode.next;
        }
        System.out.println(head);
        ListNode reversedListA = ReverseList(head);
        ListNode reversedListB = solutionB(head);
        System.out.println(reversedListB);
    }


    public static ListNode solutionA (ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode newHead = solutionA(head.next);
        // This will cause input parameter be changed
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public static ListNode ReverseList (ListNode head) {
        // write code here
        if(head == null) {
            return null;
        }
        ListNode newHead = new ListNode(0);
        linkReverse(head, newHead);
        return newHead;
    }

    static ListNode linkReverse(ListNode head, ListNode newHead){
        if(head.next == null) {
            newHead.val = head.val;
            return newHead;
        }
        ListNode pre = linkReverse(head.next, newHead);
        pre.next = new ListNode(head.val);
        return pre.next;
    }


    public static ListNode solutionB(ListNode head) {
        ListNode p1 = head;
        ListNode p2 = null;

        while(p1 != null) {
            ListNode temp = p1.next;
            p1.next = p2;
            p2 = p1;
            p1 = temp;
        }
        return p2;
    }

    /**
     * Avoid change input parameter ListNode head
     * */
    public static ListNode solutionB2 (ListNode head) {
        ListNode cur = head;
        ListNode next = null;
        ListNode newListNode = new ListNode(head.val);
        while (cur != null) {
            ListNode temp = cur.next;
            newListNode.next = next;
            next = newListNode;
            if(cur.next != null) {
                newListNode = new ListNode(cur.next.val);
            }
            cur = temp;
        }
        return next;
    }

    /**
     * 描述
     * 将一个节点数为 size 链表 m位置到n 位置之间的区间反转，要求时间复杂度O(n)，空间复杂度O(1)
     *
     * 例如：
     * 给出的链表为 1→2→3→4→5→NULL m=2,n=4
     * 返回 1→4→3→2→5→NULL
     * 数据范围：链表长度 0<size≤1000, 0<m≤n≤size,
     * 链表中每个节点的值满足 ∣val∣≤1000
     * */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        ListNode cur = newHead;
        ListNode st = null;
        for(int i=1;i<=m;i++) {
            if(i==m) {
                st = cur;
            }
            cur = cur.next;
        }

        ListNode pre = null;
        for(int i=m;i<=n;i++) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }

        st.next.next = cur;
        st.next = pre;

        return newHead.next;
    }


}